Këbab

Limit pamięci: 128 MB

Bajtazar jest redaktorem nowego portalu internetowego poświęconego gastronomii w Bajtogrodzie. Wymyślił właśnie temat, który, jeśli zostanie rzetelnie opracowany, może znacząco zwiększyć popularność serwisu. Mianowicie, Bajtazar wpadł na pomysł stworzenia rankingu bajtogrodzkich barów serwujących këbaby.

W Bajtogrodzie jest skrzyżowań, ponumerowanych liczbami od do . Skrzyżowania połączone są dwukierunkowymi drogami o różnych długościach. Wiadomo, że między dowolnymi dwoma skrzyżowaniami można przejechać na dokładnie jeden sposób. Przy każdym skrzyżowaniu znajduje się dokładnie jeden bar z këbabami.

Ponieważ w każdym lokalu kucharze serwują równie smaczne i tanie këbaby, to rozstrzygającym kryterium w rankingu stał się koszt dowozu posiłku do klienta. Bajtazar zebrał dokładne informacje na temat barów i zanotował, że lokal przy -tym skrzyżowaniu dostarcza posiłki bezpłatnie tylko do skrzyżowań odległych od niego o nie więcej niż . Początkowo założył, że najwięcej punktów w kategorii "dostawa" otrzyma ten dostawca, który dojeżdża najdalej. Wkrótce zmienił jednak zdanie, gdyż słusznie zauważył, że znacznie lepiej oceniać lokale po liczbie skrzyżowań, do których këbab może być dostarczony z lokalu bezpłatnie. Twoim zadaniem jest znaleźć tę liczbę dla każdego lokalu.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę skrzyżowań w Bajtogrodzie. W drugim wierszu znajduje się liczb całkowitych () oznaczających maksymalne odległości przy bezpłatnej dostawie dla kolejnych barów. W -tym z kolejnych wierszy znajdują się trzy liczby całkowite (), oznaczające, że skrzyżowania i są połączone drogą o długości .

W testach wartych punktów zachodzi warunek .

W testach wartych punktów istnieje co najwyżej jedno skrzyżowanie, z którego wychodzą więcej niż dwie ulice. Dodatkowo w tych testach zachodzi warunek .

Wyjście

Na wyjście należy wypisać wierszy; w -tym z nich powinna znaleźć się liczba skrzyżowań, do których -ty bar z këbabami dostarcza jedzenie bezpłatnie.

Przykład

Dla danych wejściowych:

5
2 3 3 6 5
1 2 2
2 3 1
3 4 3
4 5 2

poprawną odpowiedzią jest:

2
3
4
5
3

Zadanie(utrudnione) zapożyczone z USACO DEC12.